CS254Fall 2011Lecture Notes

Videos of lectures are available. As they are on my office machine and I don't want robots to try to download them, the directory is password protected. The login is guest and the password is guest.

Below are my lecture notes for the class so far. They should serve as a rough guide to what was covered on any given day. Frequently, however, I say more in class than is in these notes. Also, I tend to dynamically correct typos on the board that might appear in these lecture notes. So caveat emptor.

Week 1: [Aug 24 - Notation, Languages, Big-Oh]

Week 2: [Aug 29 - TMs and their Expressive Power] [Aug 31 - Efficiency]

Week 3: [Sep 5 - Labour Day] [Sep 7 - Universal Turing Machines, Uncomputability]

Week 4: [Sep 12 - O(T log T) Universal Simulation] [Sep 14 - NP and NP-completeness]

Week 5: [Sep 19 - NP-completeness] [Sep 21 - Finish Cook-Levin]

Week 6:[Sep 26 -NP-completeness, coNP, EXP versus NEXP]

Week 7: [Oct 3 - Midterm] [Oct 5 - In Banff]

Week 8: [Oct 10 - Diagonalization] [Oct 12 - Ladner's Theorem, Baker, Gill, Solovay]

Week 9: [Oct 17 - Space Complexity] [Oct 19 - Relationships between Space Complexity Classes]

Week 10: [Oct 24 - Polynomial Hierarchy] [Oct 26 - More Polynomial Hierarchy]

Week 11: [Oct 31 - Finishing Time-Space Trade-off, an Oracle Definition of PH] [Nov 2 - Practice Midterm II (also finished last day's slides)]

Week 12: [Nov 7 - Midterm II ] [Nov 9 - Oberwolfach]

Week 13: [Nov 14 - Circuits (Double Lecture)] [Nov 16 - Guest Lecturer, Eric Miles ]

Week 14: [Nov 21 - Randomized Complexity Classes] [Nov 23 - Randomized Algorithms, Error Reduction, Relationships]

Week 15: [Nov 28 - BPP and the Polynomial Hierarchy, Interactive Proofs][Nov 30 - More Interactive Proofs]

Week 16: [Dec 5 - Finish Interactive Proofs]